package com.zhugang.week08;

import java.util.ArrayList;
import java.util.List;

/**
 * @program algorithms
 * @description: restoreIpAddresses
 * @author: chanzhugang
 * @create: 2022/08/19 18:46
 */
public class RestoreIpAddresses {

    /**
     * 93 复原IP地址
     *
     * @param s
     * @return
     */
    private List<String> result = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        /**
         * s 用.切割成有效ip地址 （4个整数组成，每个整数位于0-255）
         * 穷举所有可能情况，想到用回溯
         */
        backtrack(s, 0, 0, new ArrayList<>());
        return result;
    }

    /**
     * @param s
     * @param k    下标
     * @param step 阶段
     * @param path 路径
     */
    private void backtrack(String s, int k, int step, List<Integer> path) {
        if (k == s.length() && step == 4) {
            // path to string
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 3; i++) {
                sb.append(path.get(i) + ".");
            }
            sb.append(path.get(3));
            result.add(sb.toString());
            return;
        }
        if (k == s.length() || step > 4) {
            return;
        }

        int val = 0;
        // 1位数
        if (k < s.length()) {
            val = val * 10 + (s.charAt(k) - '0');
            path.add(val);
            backtrack(s, k + 1, step + 1, path);
            path.remove(path.size() - 1);
        }
        // 不能为前导0
        if (s.charAt(k) == '0') {
            return;
        }

        // 2位数
        if (k + 1 < s.length()) {
            val = val * 10 + (s.charAt(k + 1) - '0');
            path.add(val);
            backtrack(s, k + 2, step + 1, path);
            path.remove(path.size() - 1);
        }

        // 3位数
        if (k + 2 < s.length()) {
            val = val * 10 + (s.charAt(k + 2) - '0');
            if (val <= 255) {
                path.add(val);
                backtrack(s, k + 3, step + 1, path);
                path.remove(path.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        RestoreIpAddresses restoreIpAddresses = new RestoreIpAddresses();
        List<String> result = restoreIpAddresses.restoreIpAddresses("25525511135");
        for (String s : result) {
            System.out.println(s);
        }
    }
}